package com.sheng.leetcode.year2023.month04.day12;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/04/17
 * <p>
 * 1147. 段式回文<p>
 * <p>
 * 你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:<p>
 * subtexti 是 非空 字符串<p>
 * 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )<p>
 * 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立<p>
 * 返回k可能最大值。<p>
 * <p>
 * 示例 1：<p>
 * 输入：text = "ghiabcdefhelloadamhelloabcdefghi"<p>
 * 输出：7<p>
 * 解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。<p>
 * <p>
 * 示例 2：<p>
 * 输入：text = "merchant"<p>
 * 输出：1<p>
 * 解释：我们可以把字符串拆分成 "(merchant)"。<p>
 * <p>
 * 示例 3：<p>
 * 输入：text = "antaprezatepzapreanta"<p>
 * 输出：11<p>
 * 解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。<p>
 * <p>
 * 提示：<p>
 * 1 <= text.length <= 1000<p>
 * text 仅由小写英文字符组成<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/longest-chunked-palindrome-decomposition">1147. 段式回文</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1147 {

    @Test
    public void test01() {
//        String text = "ghiabcdefhelloadamhelloabcdefghi";
//        String text = "merchant";
        String text = "antaprezatepzapreanta";
        System.out.println(new Solution().longestDecomposition(text));
    }
}

class Solution {
    /**
     * 我们可以从字符串的两端开始，寻找长度最短的、相同且不重叠的前后缀：
     * 如果找不到这样的前后缀，那么整个字符串作为一个段式回文，答案加1；
     * 如果找到了这样的前后缀，那么这个前后缀作为一个段式回文，答案加2，
     * 然后继续寻找剩下的字符串的前后缀。
     * 以上贪心策略的证明如下：
     * 假设有一个前后缀A1 和A2满足条件，又有一个前后缀B1和B4满足条件，由于A1=A2，且B1 = B2，
     * 那么有 B3 = B1 = B4 = B2，并且 C1 = C2，因此，如果我们贪心的将 B1 和 B4 分割出来，
     * 那么剩下的 C1 和 C2，以及 B2和 B3 也能成功分割。
     * 因此我们应该贪心地选择长度最短的相同前后缀进行分割，这样剩余的字符串中，将可能分割出更多的段式回文串。
     * <p>
     * 作者：lcbin
     * 链接：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition/solution/python3javacgotypescript-yi-ti-shuang-ji-ttp1/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param text
     * @return
     */
    public int longestDecomposition(String text) {
        int ans = 0;
        for (int i = 0, j = text.length() - 1; i <= j; ) {
            boolean ok = false;
            for (int k = 1; i + k - 1 < j - k + 1; ++k) {
                if (check(text, i, j - k + 1, k)) {
                    ans += 2;
                    i += k;
                    j -= k;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                ++ans;
                break;
            }
        }
        return ans;
    }

    private boolean check(String s, int i, int j, int k) {
        while (k-- > 0) {
            if (s.charAt(i++) != s.charAt(j++)) {
                return false;
            }
        }
        return true;
    }
}
